package special;

import java.util.*;

class FoodRatings {
    Map<String, String> foodToC;
    Map<String, Integer> foodToRating;
    Map<String, TreeMap<Integer, TreeSet<String>>> cuToRat;

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        int n = foods.length;
        foodToRating = new HashMap<>();
        foodToC = new HashMap<>();
        for (int i = 0; i < n; i++) {
            foodToRating.put(foods[i], ratings[i]);
            foodToC.put(foods[i], cuisines[i]);
        }
        cuToRat = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (cuToRat.containsKey(cuisines[i])){
                TreeMap<Integer, TreeSet<String>> map2 = cuToRat.get(cuisines[i]);
                if (map2.containsKey(ratings[i])){
                    map2.get(ratings[i]).add(foods[i]);
                }else {
                    TreeSet<String> set = new TreeSet<>();
                    set.add(foods[i]);
                    map2.put(ratings[i], set);
                }
            }else {
                TreeMap<Integer, TreeSet<String>> map1 = new TreeMap<>((o1, o2) -> o2 - o1);
                TreeSet<String> set2 = new TreeSet<>();
                set2.add(foods[i]);
                map1.put(ratings[i], set2);
                cuToRat.put(cuisines[i], map1);
            }
        }
    }
    
    public void changeRating(String food, int newRating) {
        String c = foodToC.get(food);
        Integer pre = foodToRating.get(food);
        cuToRat.get(c).get(pre).remove(food);

        foodToRating.put(food, newRating);
        if (cuToRat.get(c).containsKey(newRating)){
            cuToRat.get(c).get(newRating).add(food);
        }else {
            TreeSet<String> set = new TreeSet<>();
            set.add(food);
            cuToRat.get(c).put(newRating, set);
        }
    }
    
    public String highestRated(String cuisine) {
        TreeMap<Integer, TreeSet<String>> fat = cuToRat.get(cuisine);
        while (fat.firstEntry().getValue().size() == 0){
            fat.pollFirstEntry();
        }
        return fat.firstEntry().getValue().first();
    }
}